package dp

// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
// 题解: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/zui-jia-mai-mai-gu-piao-shi-ji-han-leng-dong-qi-4/
// 最佳买卖股票时机含冷冻期
// 算法：动态规划
// 注意：这道题因为买入和卖出的时机非常紧密，所以DP 需要考虑更多种状态
// f0 表示操作后，持有一只股票的最大收益（特别注意是操作后，后续的两种状态也都表示操作后）
// f1 表示操作后，没有持股，并且将处于冷冻期的最大收益
// f2 表示操作后，没有持股，并且将不处于冷冻期的最大收益
// 三种状态的转换公式:
// f0[n] = max(f0[n-1], f2[n-1] - prices[n]) (之前就持有，或者非冷冻期购买)
// f1[n] = f0[n-1] + prices[n]
// f2[n] = max(f2[n-1], f1[n-1]) (上一个状态就没卖股票，或者过了冷冻期)
// 注意到当前状态只和前一位状态有关，所以也可以不用数组，节省空间
// 时间复杂度: O(n)
func MaxProfitWithCoolDown(prices []int) int {
	if 0 == len(prices) {
		return 0
	}
	var f0, f1, f2 int
	f0 = -prices[0]
	f1, f2 = 0, 0

	for index := 1; index < len(prices); index++ {
		oldF0, oldF1 := f0, f1
		f0 = maxInt(f0, f2-prices[index])
		f1 = oldF0 + prices[index]
		f2 = maxInt(oldF1, f2)
	}

	return maxInt(f1, f2) // 最后要满足最大收益，手头一定是没有持股的
}

// func maxInt(a, b int) int {
// 	if a > b {
// 		return a
// 	}
// 	return b
// }
